package linkedqueue

/*
Copyright @2016 by No.20(zdt3476@163.com)

Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at

http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
*/

// LinkedQueue is a ring queue
type LinkedQueue struct {
	values []interface{}
	front  int
	rear   int
	size   int
}

const (
	defaultSize = 10
)

// New return a pointer to Queue
func New(param ...int) *LinkedQueue {
	var size int
	if len(param) == 1 {
		size = param[0]
	} else {
		size = defaultSize
	}
	return &LinkedQueue{
		values: make([]interface{}, size),
		front:  0,
		rear:   0,
		size:   0,
	}
}

// Size return the queue's size
func (q *LinkedQueue) Size() int {
	return q.size
}

// Cap return the queue's capacity
func (q *LinkedQueue) Cap() int {
	return cap(q.values)
}

// Empty return whether queue empty is
func (q *LinkedQueue) Empty() bool {
	return q.Size() == 0
}

// Push add a value to queue
func (q *LinkedQueue) Push(v interface{}) {
	if q.rear == q.front && q.size > 0 {
		newValues := make([]interface{}, q.size*2)
		copy(newValues, q.values[q.rear:])
		copy(newValues[len(q.values)-q.front:], q.values[:q.front])
		q.front = 0
		q.rear = len(q.values)
		q.values = newValues
	}
	q.values[q.rear] = v
	q.size++
	q.rear = (q.rear + 1) % cap(q.values) // 这里cap和len是一样的效果
}

// Pop return a value from top of queue
// and remove it
func (q *LinkedQueue) Pop() interface{} {
	defer func() {
		q.front++
		q.size--
	}()
	return q.Top()
}

// Top return a value from top of queue
func (q *LinkedQueue) Top() interface{} {
	return q.values[q.front]
}

// Contains return whether contain item is
// 效率低
func (q *LinkedQueue) Contains(item interface{}) bool {
	begin, end := 0, q.Size()-1
	for begin <= end {
		if q.values[begin] == item {
			return true
		}
		if q.values[end] == item {
			return true
		}
		begin++
		end--
	}

	return false
}
